// https://leetcode.cn/problems/solving-questions-with-brainpower/description/?envType=daily-question&envId=2025-04-01

// 算法思路总结：
// 1. 记忆化搜索解决带跳过的最大得分问题
// 2. 每个问题有两种选择：解答（得分+跳过brainpower个问题）或跳过
// 3. 递归计算两种选择的最大得分
// 4. 使用memo数组避免重复计算子问题
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    long long memo[100001];

    long long mostPoints(vector<vector<int>>& questions) 
    {
        memset(memo, -1, sizeof(memo));

        return dfs(questions, 0);
    }

    long long dfs(vector<vector<int>>& questions, int pos)
    {
        if (pos >= questions.size())
        {
            return 0;
        }

        if (memo[pos] != -1)
        {
            return memo[pos];
        }

        long long ret = questions[pos][0] + dfs(questions, pos + 1 + questions[pos][1]);
        ret = max(ret, dfs(questions, pos + 1));

        return memo[pos] = ret;
    }
};

int main()
{
    vector<vector<int>> questions1 = {
        {3,2},
        {4,3},
        {4,4},
        {2,5}
    };

    vector<vector<int>> questions2 = {
        {1,1},
        {2,2},
        {3,3},
        {4,4},
        {5,5}
    };

    Solution sol;

    cout << sol.mostPoints(questions1) << endl;
    cout << sol.mostPoints(questions2) << endl;

    return 0;
}